package com.yuan.algorithms.动态规划;

import java.util.*;

import static java.util.Collections.*;

/**
 * @author YouYuan
 * @contact 1265161633@qq.com
 * @descript 一个正在抢劫商店的小偷发现了n个商品，第i个商品价值v[i]美元，重w[i]磅，v[i]和w[i]都是整数．
 * 这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅重的商品，W是一个整数．他应该拿哪些商品才能最大化价值呢？
 * （我们称这个问题是O-1背包问题，因为对每个商品，小偷要么把它完整拿走，要么把它留下；他不能只拿走一个商品的一部分，或者把一个商品拿走多次。）
 */
public class 背包问题 {

	private static class Goods {
		public int price;
		public int weight;
		/**
		 * 贪心策略可以使用单位价格解决分数背包问题，但是不适合0-1背包问题
		 */
		public double avgPrice;

		public Goods(int price, int weight) {
			this.price = price;
			this.weight = weight;
			this.avgPrice = (double) price / weight;
		}
	}

	public static void main(String[] args) {
//		int[] v = {60, 100, 120};//商品价值
//		int[] w = {10, 20, 30};//商品重量
		int[] v = {10, 20, 30, 40, 50, 60, 60, 20,20,20};//商品价值
		int[] w = {5, 5, 20, 15, 20, 30, 20,5,5,5};//商品重量
		int W = 50;//背包最大承受重量

		List[][] result = new ArrayList[v.length+1][W +1];
		//cost[i][j]表示背包容量为j时在i个商品中能取到的最大价值
		int[][] cost = dp(v, w, W, result);

		System.out.println(cost[v.length][W]);
		System.out.println(result[v.length][W]);


		boolean[] mark = new boolean[v.length];//用于标记是否选取对应的商品，此标记存在重复标记的问题，结果不准确，仅供测试
		System.out.println(f(v, w, W, mark, 0, 0));
		for (int i = 0; i < mark.length; i++) {
			if (mark[i]) {
				System.out.print(v[i]+" ");
			}
		}
	}

	/**
	 * 动态规划递推求解
	 * 设c[i,j]代表总容量为j的背包中装下的总共i种商品的最大总价值，则0-1背包问题的目标是获得c[n,W]的最大值，其中n是可选商品的种类，W是背包总容量。则0-1背包问题的最优子结构为：
	 * 1、如果最优解包含第n种商品，则接下来需要解决子问题：背包剩余容量为W-wn，需要在前n-1种商品中作出选择并得出最优解。
	 * 2、如果最优解不包含第n种商品，则接下来需要解决子问题：背包剩余容量为W，需要在前n-1种商品中作出选择并得出最优解。
	 * 综上所述，c[i,j]的递推式为：
	 * c[i,j]=max{c[i-1,j]，c[i-1,j-wi]+vi}
	 * @param v
	 * @param w
	 * @param weight 背包最大承受重量
	 * @param result 记录拿取的商品
	 * @return
	 */
	private static int[][] dp(int[] v, int[] w, int weight, List[][] result) {
		int[][] cost = new int[v.length+1][weight +1];
		for (int i = 1; i <= v.length; i++) {
			for (int j = 1; j <= weight; j++) {
				if (j >= w[i-1]) {
					/**
					 * cost[i - 1][j - w[i-1]] + v[i-1] ：取当前商品，背包剩余容量为W-wn，前n-1种商品在容量为W-wn的最大价值加上当前商品价值
					 * cost[i - 1][j] ：不取当前商品可得最大价值，即容量不变，前n-1种商品的最大价值
					 */
					int add = cost[i - 1][j - w[i - 1]] + v[i - 1];
					int pre = cost[i - 1][j];
					ArrayList<Object> list = new ArrayList<>();
					if (add > pre) {
						list.addAll(Optional.ofNullable(result[i - 1][j - w[i - 1]]).orElse(new ArrayList()));
						list.add(v[i - 1]);
					} else {
						list.addAll(Optional.ofNullable(result[i - 1][j]).orElse(new ArrayList()));
					}
					result[i][j] = list;
					cost[i][j] = Math.max(add, pre);
				} else {
					result[i][j] = result[i - 1][j];
					cost[i][j] = cost[i - 1][j];
				}
			}
		}
		return cost;
	}

	/**
	 * 递归解法，因为递归包含了大量中间结果的重复计算，只要数据集稍微大一点，计算复杂度呈指数级增加，所以运行效率低
	 * 计算背包能够装下的最大价值
	 * @param v 商品价值
	 * @param w 商品重量
	 * @param space 剩余空间
	 * @param mark 标记数组
	 * @param current 当前位置
	 * @param cost 当前价值总值
	 */
	private static int f(int[] v, int[] w, int space, boolean[] mark, int current, int cost) {
		if (space <= 0 || current >= v.length) {
			return cost;
		}
		int cost_1 = 0;
		int cost_2 = 0;
		if (space - w[current] >= 0) {
			//选择当前商品，空间减去当前重量，总价值加上当前价值，继续查看下一个商品
			mark[current] = true;
			cost_1 = f(v, w, space - w[current], mark, current+1, cost+v[current]);
		}
		//不选择当前商品，空间和总价值不变，继续看下一个商品
		mark[current] = false;
		cost_2 = f(v, w, space, mark, current+1, cost);

		// 比较挑选当前商品和不挑选当前商品能达到的总价值，挑选当前商品可达总价值大于不挑选，则标记当前商品选取状态
		if (cost_1 > cost_2) {
			mark[current] = true;
			return cost_1;
		} else {
			mark[current] = false;
			return cost_2;
		}
	}
}
